package array

import "math"

/*
	给定一个数组 prices
	它的第 i 个元素 prices[i]表示一支给定股票第 i 天的价格。
	你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。
	设计一个算法来计算你所能获取的最大利润。
	返回你可以从这笔交易中获取的最大利润。
	如果你不能获取任何利润，返回 0 。
*/

func MaxProfit(prices []int) int {

	// 方法一 但是超出了时间限制
	// max := 0

	// for i := 0; i < len(prices)-1; i++ {
	// 	for j := i + 1; j < len(prices); j++ {
	// 		if prices[j]-prices[i] > max {
	// 			max = prices[j] - prices[i]
	// 		}
	// 	}
	// }

	// return max

	// 方法二
	minPrice := math.MaxInt64
	res := 0

	for _, price := range prices {
		if price-minPrice > res {
			res = price - minPrice
		}

		if price < minPrice {
			minPrice = price
		}
	}

	return res
}
